/*
 * @lc app=leetcode.cn id=72 lang=cpp
 *
 * [72] 编辑距离
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) return n + m;

        vector<vector<int>> DP(n + 1, vector<int>(m + 1));
        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            DP[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            DP[0][j] = j;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = DP[i - 1][j] + 1;
                int down = DP[i][j - 1] + 1;
                int left_down = DP[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]){
                    left_down += 1;
                }
                DP[i][j] = min(left, min(down, left_down));
            }
        }
        return DP[n][m];
    }
};

// dp[i][j]: 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数

// 当word1[i]==word2[j]时:
//      dp[i-1][j-1]：  word1的[0,i-1]位置与word2的[0,j-1]位置的字符已匹配, 又word1[i]==word2[j], 因此不用执行操作
// 当word1[i]!=word2[j]时:
//      dp[i-1][j-1]+1: word1的[0,i-1]位置与word2的[0,j-1]位置的字符已匹配, 加1代表执行word1[i]->word2[j]的替换操作
//      dp[i-1][j]+1:   word1的[0,i-1]位置与word2的[0,j]位置的字符已匹配, 加1代表执行word1[i]的删除操作
//      dp[i][j-1]+1：  word1的[0,i]位置与word2的[0,j-1]位置的字符已匹配, 加1代表执行word1[i]的插入操作
//
// (一)、当word1[i]==word2[j]时,由于遍历到了i和j,说明word1的0~i-1和word2的0~j-1的匹配结果已经生成,
// 由于当前两个字符相同,因此无需做任何操作,dp[i][j]=dp[i-1][j-1]
// (二)、当word1[i]!=word2[j]时,可以进行的操作有3个:
//       ① 替换操作:可能word1的0~i-1位置与word2的0~j-1位置的字符都相同,
//            只是当前位置的字符不匹配,进行替换操作后两者变得相同,
//            所以此时dp[i][j]=dp[i-1][j-1]+1(这个加1代表执行替换操作)
//       ②删除操作:若此时word1的0~i-1位置与word2的0~j位置已经匹配了,
//          此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)
//          和word2的0~j位置匹配,因此此时dp[i][j]=dp[i-1][j]+1(这个加1代表执行删除操作)
//       ③插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配,
//           此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得
//           此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,
//           所以此时dp[i][j]=dp[i][j-1]+1(这个加1代表执行插入操作)
//       ④由于题目所要求的是要最少的操作数:所以当word1[i] != word2[j] 时,
//           需要在这三个操作中选取一个最小的值赋格当前的dp[i][j]
// (三)总结:状态方程为:
// if(word1[i] == word2[j]):
//       dp[i][j] = dp[i-1][j-1]
// else:
//        min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
// @lc code=end

